In an interconnected communications network, e.g., the Internet, routing protocols are used by routers to decide where to forward packets of information, e.g., IP packets. Within each area of an autonomous system, an interior routing protocol computes the shortest path between any two routers in the area. The most widely used interior routing protocol is Open Shortest Path First (OSPF) such as described in J. Moy, OSPF Version 2, INTERNET DRAFT, rfc 2178, Jul. 1997 the contents and disclosure of which is wholly incorporated by reference as if fully set forth herein. Routers in an OSPF area exchange link state information periodically so that each router has a complete description of the topology of the area. Each router then computes the shortest path tree (SPT) from itself to every other router in the area by an algorithm, e.g., Dijkstra's algorithm, such as described in E. Dijkstra "A note two problems in connection with graphs," Numerical Mathematics, vol.1, 1959, p. 269-271, the contents and disclosure of which is wholly incorporated by reference as if fully set forth herein. The corresponding SPT is then used to build a routing table which contains the next hop for any destination.
To illustrate, as shown in FIG. 1, a network 10 comprises a set of nodes or routers 15. The shortest path will be computed from a source node, e.g., node "A", that sends a packet along one or more links 20 to a destination node, e.g., node "C". A weight (or distance) is associated with each link and the shortest path tree is computed from the knowledge of the sum of the weights associated with links comprising each of the various paths between the source and destination node. Some of the well-known computation algorithms for determining the shortest path trees is Dijkstra's algorithm, as mentioned above, the Bellman-Ford algorithm such as described in Richard Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, vol. 16, 1958, p. 87-90, and, D'Esopo-Pape as described in D. Bertsekas Linear Network Optimization: Algorithms and Codes The MIT Press, Cambridge, Mass. The contents and disclosure of both of these references are incorporated herein by reference.
The characterization of each of these algorithms is as follows: When the topology of the area network 10 changes (a link fails, recovers, or changes its routing cost), every router in the area is notified of the change. After making the corresponding changes to its topology data structure, each router must recompute its SPT. Currently this recomputation is done by deleting the current SPT and rebuilding it from scratch again, e.g., by using any of the above-mentioned algorithms.
Current recomputation techniques implemented in routers are inefficient because they do not make use of the structure of the previous SPT and instead construct an entirely new SPT without using any information of the previous SPT trees. After a single link state change, the SPT does not usually change by much (oftentimes it does not change at all). By starting the calculation from scratch, OSPF has to recalculate all the parts of the SPT that need not change.
Given a router's topology data structure, it often contains multiple shortest path trees from the router itself. By starting the calculation from scratch, a router may choose a completely different SPT after link state updates, even thought the necessary changes to obtain a new SPT are just a few links. As a result of the completely different SPT, the traffic load in the network may become unstable, which is not a desirable phenomenon.
It would be highly desirable to implement an incremental shortest path computation algorithm that is fast and requires a minimum number of changes to the existing shortest path tree structure after a link state is updated.
Moreover, it would be highly desirable to transform conventional static shortest path tree computation algorithms into corresponding dynamic ones.